package leo.mystudy.leetcode;

import leo.mystudy.pojo.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author leo
 * @version 1.0.0
 * @description 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：[[3],[9,20],[15,7]]
 * 示例 2：
 * <p>
 * 输入：root = [1]
 * 输出：[[1]]
 * 示例 3：
 * <p>
 * 输入：root = []
 * 输出：[]
 *  
 * <p>
 * 提示：
 * <p>
 * 树中节点数目在范围 [0, 2000] 内
 * -1000 <= Node.val <= 1000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @create 2022/3/12 17:52
 */
public class No102LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        List<TreeNode> list = new LinkedList<>();
        list.add(root);
        while (!list.isEmpty()) {
            List<Integer> intList = new LinkedList<>();
            List<TreeNode> nodeList = new LinkedList<>();
            for (TreeNode node : list) {
                intList.add(node.val);
                if (node.left != null) {
                    nodeList.add(node.left);
                }
                if (node.right != null) {
                    nodeList.add(node.right);
                }
            }
            result.add(intList);
            list.clear();
            list = nodeList;
        }
        return result;
    }

//    public List<List<Integer>> levelOrder(TreeNode root) {
//        if (root == null) {
//            return new ArrayList<>();
//        }
//        Map<Integer, List<Integer>> map = new HashMap<>();
//        preOrder(root, 0, map);
//        return map.entrySet().stream().sorted((Map.Entry.comparingByKey())).map(Map.Entry::getValue).collect(Collectors.toList());
//    }
//
//    private void preOrder(TreeNode node, int depth, Map<Integer, List<Integer>> map) {
//        if (node == null) {
//            return;
//        }
//        map.computeIfAbsent(depth, t -> new ArrayList<>()).add(node.val);
//        preOrder(node.left, depth + 1, map);
//        preOrder(node.right, depth + 1, map);
//    }


}
